import Node from "./Node.js";
import LinkedList from "./LinkedList.js";

export default class CircularLinkedList extends LinkedList {
  constructor() {
    super();
  }

  /**
   * 将元素插入到链表的指定位置，如果失败则返回null
   * @param {*} value 需要插入的项
   * @param {number} index 需要插入的位置
   * @returns {LinkedList|null}
   */
  insert(value, index) {
    // 可插入位置为head前面到tail后面，因此index的最大值应该比链表的下标范围大1，即this.count的大小
    if (index < 0 || index > this.count) {
      return null;
    }

    const newNode = new Node(value);

    if (index === 0) {
      // 如果index为0，则将此节点加入到原head节点前面
      newNode.next = this.head;
      this.head = newNode;

      // 如果不存在tail，则说明此前链表为空链表，此时将tail和head将是同一个节点
      if (!this.tail) {
        this.tail = newNode;
        this.head.next = this.head;
      }

      this.tail.next = newNode;
    } else if (index === this.count) {
      // 将元素插入到tail后面
      newNode.next = this.head;
      this.tail.next = newNode;
      this.tail = newNode;
    } else {
      // 将元素插入到链表中间的某个位置
      let prevNode = find(index - 1);
      newNode.next = prevNode.next;
      prevNode.next = newNode;
    }

    this.count++;

    return this;
  }

  /**
   * 删除元素
   * @param {*} value 需要删除的项
   * @returns {Node|null}
   */
  remove(value) {
    if (!this.head) {
      return null;
    }

    let currentNode = this.head;
    let prevNode = null; // 用来存储被删除节点的前一个节点

    for (let i = 0; i < this.count; i++) {
      if (value === currentNode.value) {
        if (currentNode === this.head) {
          // 当前节点为head时
          // 将head设置为被删除节点的下一个节点
          this.head = currentNode.next;
          this.tail.next = this.head; // 将tail.next指向新的head节点

          // 此时链表只有一个节点，即head，tail都为同一个节点
          if (currentNode === this.tail) {
            this.tail = null;
          }
        } else if (currentNode === this.tail) {
          // 当前节点与tail节点相同
          this.tail = prevNode;
          this.tail.next = this.head;
        } else {
          prevNode.next = currentNode.next;
        }

        this.count--;
        return currentNode;
      }

      prevNode = currentNode;
      currentNode = currentNode.next;

      // 表示循环了一圈，并未找到需要删除的内容，需要将currentNode设置为null，防止返回错误的结果
      if (i === this.count - 1 && currentNode === this.head) {
        currentNode = null;
      }
    }

    return currentNode;
  }

  /**
   * 按指定位置删除元素
   * @param {number} index 需要删除元素的位置
   * @returns {Node|null}
   */
  removeAt(index) {
    if (index < 0 || index >= this.count) {
      return null;
    }

    let removeNode = this.head;

    if (this.count === 1) {
      // 如果链表长度只有1，则相当于清空链表
      this.head = null;
      this.tail = null;
    } else if (index === 0) {
      // 删除头部节点
      this.head = this.head.next;
      this.tail.next = this.head;
    } else if (index === this.count - 1) {
      // 删除尾部节点
      let prevNode = this.findAt(index - 1);
      removeNode = this.tail;
      prevNode.next = this.head;
      this.tail = prevNode;
    } else {
      let prevNode = this.findAt(index - 1);
      removeNode = prevNode.next;
      prevNode.next = removeNode.next;
    }

    this.count--;

    return removeNode;
  }

  /**
   * 将链表转化为数组并返回
   * @returns {Node[]}
   */
  toArray() {
    const nodes = [];

    for (let i = 0, currentNode = this.head; i < this.count; i++) {
      nodes.push(currentNode);
      currentNode = currentNode.next;
    }

    return nodes;
  }
}
